#include<stdbool.h>
#define base 769
typedef struct ListNode datatype;
struct hashlist 
{
    datatype key;
    struct hashlist* Next;
};
typedef struct 
{
    struct hashlist* hashtable[base];//定义哈希数组的大小
} MyHashSet;

bool isInHash(struct hashlist* list, struct  ListNode* item) 
{
    struct hashlist* cur=list;//遍历链表
    while (cur != NULL) 
    {
        if (cur->key.next == item) //找节点
        {
            return true;
        }
        cur = cur->Next;
    }
    return false;
}
MyHashSet* myHashSetCreate() 
{
    int i=0;
    MyHashSet* myhashtable= (MyHashSet* )malloc(sizeof(MyHashSet));
    /* 对链表的头结点赋初值 */
    for (i = 0; i < base; i++)
    {
        myhashtable->hashtable[i] = NULL;
    }
    return myhashtable;
}


void HashAdd(MyHashSet* obj, struct  ListNode* item) 
{
    //插入在Head处
    if(isInHash(obj->hashtable[(int)(size_t)item % base],item))
        //如果单纯使用（int）会导致指针位数不够，转换成8字节
    {
        //不用添加了
        return;
    }
    struct hashlist* temp = (struct hashlist*)malloc(sizeof(struct hashlist));
    temp->key.next = item;
    temp->Next = NULL;
    if(obj->hashtable[(int)(size_t)item%base] != NULL)
    {
        //当前头链表不为空，则需要将后续的链表接上
        //需要主要这里表头也代表一个数据的值
        temp->Next = obj->hashtable[(int)(size_t)item%base];
    }
    //修改头链表
    obj->hashtable[(int)(size_t)item%base] =  temp;

}
bool myHashSetContains(MyHashSet* obj, struct  ListNode *item) 
{
    return isInHash(obj->hashtable[(int)(size_t)item%base],item);
}

bool hasCycle(struct ListNode* head ) {
    struct ListNode* cur = head;
    MyHashSet* myhashtable  = myHashSetCreate(); 
    while (cur != NULL) 
    {
        if(myHashSetContains(myhashtable,cur))//判断在不在哈希中
        {
            return true;
            //cur即当前入环的节点
        }
        else
        {
            HashAdd(myhashtable ,cur);
        }
        cur = cur->next;
    }
    return false;   
}
